package linkedlist.other;

import linkedlist.Node;
import linkedlist.create.RecursionLinkedCreator;
import linkedlist.iterator.LoopIterator;

import java.util.Arrays;

/**
 * @Author wangtengyu
 * @Create 2018-09-05-9:08 合并两个有序链表
 */
public class MergeLinkedList {

  /**
   * 递归合并两个有序链表
   */
  public Node mergeLinkedList(Node<Integer> head1, Node<Integer> head2) {

    if (head1 == null) {
      return head2;
    }
    if (head2 == null) {
      return head1;
    }
    Node<Integer> newHead = null;
    if (head1.getData() <= head2.getData()) {
      newHead = head1;
      newHead.setNext(mergeLinkedList(head1.getNext(), head2));
    } else if (head1.getData() > head2.getData()) {
      newHead = head2;
      newHead.setNext(mergeLinkedList(head1, head2.getNext()));
    }
    return newHead;
  }


  /**
   * 迭代实现链表
   */
  public Node mergeLinkedList2(Node<Integer> head1, Node<Integer> head2) {

    //传进来为空的判断
    if (head1 == null) {
      return head2;
    }
    if (head2 == null) {
      return head1;
    }

    //定义返回的头结点
    Node<Integer> newHead = null;

    //定义第一个节点
    if (head1.getData() <= head2.getData()) {
      newHead = head1;
      head1 = head1.getNext();
    } else if (head2.getData() < head1.getData()) {
      newHead = head2;
      head2 = head2.getNext();
    }

    Node<Integer> tail = newHead;
    //当定义完第一个节点以及迭代的过程中，如果出现了空节点，要进行判断
    while (head1 != null && head2 != null) {
      if (head1.getData() <= head2.getData()) {
        tail.setNext(head1);
        head1 = head1.getNext();
      } else if (head2.getData() < head1.getData()) {
        tail.setNext(head2);
        head2 = head2.getNext();
      }
      tail = tail.getNext();
    }

    if (head1 == null) {
      tail.setNext(head2);
    } else if (head2 == null) {
      tail.setNext(head1);
    }
    return newHead;

  }


  public static void main(String[] args) {
    RecursionLinkedCreator creator = new RecursionLinkedCreator();
    MergeLinkedList merger = new MergeLinkedList();
    LoopIterator loopIterator = new LoopIterator();
    Node<Integer> node1 = creator.createlinkedList(Arrays.asList(1, 4, 7, 8, 9));
    Node<Integer> node2 = creator.createlinkedList(Arrays.asList(2, 3, 5, 6, 10));

    Node newNode = merger.mergeLinkedList2(node1, node2);
    loopIterator.iterator(newNode);


  }

}
